package 中等;

import java.util.LinkedList;

public class 二叉树的序列化与反序列化 {


    //前序遍历
    public String serialize1(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        serialize1(root,sb );
        return sb.toString();
    }

    public void serialize1(TreeNode root,StringBuffer sb){
        if (root == null){
            sb.append("#").append(",");
            return;
        }
        sb.append(root.val).append(",");
        serialize1(root.left,sb );
        serialize1(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize1(String data) {
        String[] split = data.split(",");
        LinkedList<String> linkedList = new LinkedList<>();
        for (String s : split) {
            linkedList.add(s);
        }
        return deserialize1(linkedList );
    }

    public TreeNode deserialize1(LinkedList<String> linkedList){
        if (linkedList.isEmpty()){
            return null;
        }
        String s = linkedList.removeFirst();
        if (s.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s));

        root.left = deserialize1(linkedList);
        root.right = deserialize1(linkedList);
        return root;

    }

    //后序遍历
    public String serialize2(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        serialize1(root,sb );
        return sb.toString();
    }

    public void serialize2(TreeNode root,StringBuffer sb){
        if (root == null){
            sb.append("#").append(",");
            return;
        }
        serialize2(root.left,sb );
        serialize2(root.right, sb);
        sb.append(root.val).append(",");
    }

    public TreeNode deserialize2(String data) {
        String[] split = data.split(",");
        LinkedList<String> linkedList = new LinkedList<>();
        for (String s : split) {
            linkedList.add(s);
        }
        return deserialize2(linkedList );
    }

    public TreeNode deserialize2(LinkedList<String> linkedList){
        if (linkedList.isEmpty()){
            return null;
        }
        String last = linkedList.removeLast();
        if (last.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(last));
        root.left = deserialize2(linkedList);

        root.right = deserialize2(linkedList);
        return root;

    }
}
